#include <stdlib.h>
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode {
    int val;
    struct ListNode* next;
};

/**
 * 合并两个有序单链表
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL && l2 == NULL) {
        return NULL;
    }
    if (l1 == NULL && l2 != NULL) {
        return l2;
    }
    if (l1 != NULL && l2 == NULL) {
        return l1;
    }
    struct ListNode* res = NULL;
    res = (struct ListNode*)malloc(sizeof(*res));
    res->next = NULL;
    struct ListNode* cur = res;

    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    while (l1 != NULL) {
        cur->next = l1;
        cur = cur->next;
        l1 = l1->next;
    }
    while (l2 != NULL) {
        cur->next = l2;
        cur = cur->next;
        l2 = l2->next;
    }
    return res->next;
}